﻿#pragma once
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cassert>
#include <thread>
#include <mutex>
#include <algorithm>
#include <unordered_map>
using std::cin;
using std::cout;
using std::endl;
using std::min;
using std::mutex;
using std::thread;
using std::unordered_map;
using std::unique_lock;

#ifdef _WIN64
	typedef unsigned long long SPAN_ID;
#elif _WIN32
typedef size_t SPAN_ID;
#endif

#ifdef _WIN32
#include <Windows.h>
#else

#endif

//ThreadCache的自由链表哈希桶的表大小
static const int NFREELIST = 208;

// ⼩于等于MAX_BYTES，就找thread cache申请 
// ⼤于MAX_BYTES，就直接找page cache或者系统堆申请 
static const int MAX_BYTE = 1024 * 256;

//PageCache层面上的哈希桶的表大小
static const int NPAGES = 129;

//一页有多大的维度，此处PAGE_SHFT为13，说明一页大小为8k(2^13个比特位)
static const int PAGE_SHFT = 13;


inline static void* SystemAlloc(size_t kpage)
{
	#ifdef _WIN32
		void* ptr = VirtualAlloc(0, kpage * (1 << PAGE_SHFT), MEM_COMMIT | MEM_RESERVE,
			PAGE_READWRITE);
	#else
		// linux下brk mmap等 
	#endif
		if (ptr == nullptr)
			throw std::bad_alloc();
		return ptr;
}

inline static void SystemFree(void* ptr)
{
	#ifdef _WIN32
		VirtualFree(ptr, 0, MEM_RELEASE);
	#else

	#endif
}

static inline void*& Next(void* obj)
{
	return *(void**)obj;
}

class FreeList
{
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;//记录自由链表结点个数
public:

	bool Empty()
	{
		return _freeList == nullptr;
	}

	void push(void* obj)
	{
		assert(obj);
		*(void**)obj = _freeList;
		_freeList = obj;
		++_size;
	}

	void pushRange(void* begin, void* end, size_t size)
	{
		assert(begin || end);
		Next(end) = _freeList;
		_freeList = begin;
		_size += size;
	}

	void popRange(void*& begin, void*& end, size_t size)
	{
		assert(size <= Size());
		begin = end = _freeList;
		for (size_t i = 1; i < size; ++i)
		{
			end = Next(end);
		}
		_freeList = Next(end);
		Next(end) = nullptr;
		_size -= size;
	}

	void* pop()
	{
		assert(_freeList);
		void* next = Next(_freeList);
		void* obj = _freeList;
		_freeList = next;
		--_size;
		return obj;
	}

	size_t& MaxSize()
	{
		return _maxSize;
	}

	size_t Size()
	{
		return _size;
	}
};

//管理对齐和映射等关系
class SizeClass
{
public:
	static size_t _RoundUp(size_t sz, size_t alignNum)
	{
		/*
		int n = sz % alignNum;
		if (n == 0)
		{
			return sz;
		}
		else
		{
			return (sz / alignNum + 1) * alignNum;
		}
		*/
		return (sz + alignNum - 1) & ~(alignNum - 1);
	}

	static int _Index(size_t sz, size_t align_shift)
	{		
		return (int)((sz + (1ULL << align_shift) - 1) >> align_shift) - 1;
	}

	//计算对齐后分配内存大小
	static size_t RoundUp(size_t sz)
	{
		size_t roundUpSz = -1;
		if (sz <= 128)
		{
			roundUpSz = _RoundUp(sz, 8);
		}
		else if (sz <= 1024)
		{
			roundUpSz = _RoundUp(sz, 16);
		}
		else if (sz <= 8 * 1024)
		{
			roundUpSz = _RoundUp(sz, 128);
		}
		else if (sz <= 64 * 1024)
		{
			roundUpSz = _RoundUp(sz, 1024);
		}
		else if (sz <= 256 * 1024)
		{
			roundUpSz = _RoundUp(sz, 8 * 1024);
		}
		else
		{
			roundUpSz = _RoundUp(sz, 1 << PAGE_SHFT);//大于256k的话，按页(此时是8k)对齐
		}
		return roundUpSz;
	}

	//计算对应哈希桶(ThreadCache的成员变量_freeList[NFREELIST])的下标
	static int Index(size_t sz)
	{
		static int group_array[] = { 16, 56, 56, 56, 24 };
		int index = -1;
		if (sz <= 128)
		{
			index = _Index(sz, 3);
		}
		else if (sz <= 1024)
		{
			index = _Index(sz - 128, 4) + group_array[0];
		}
		else if (sz <= 8 * 1024)
		{
			index = _Index(sz - 1024, 7) + group_array[0] + group_array[1];
		}
		else if (sz <= 64 * 1024)
		{
			index = _Index(sz - 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
		}
		else if (sz <= 256 * 1024)
		{
			index = _Index(sz - 64 * 1024, 13) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
		}
		else
		{
			assert(false);
		}
		return index;
	}

	static size_t NumMoveSize(size_t alignNum)
	{
		assert(alignNum <= MAX_BYTE);
		size_t batchNum = MAX_BYTE / alignNum;
		if (batchNum > 512)
			batchNum = 512;
		if (batchNum < 2)
			batchNum = 2;
		return batchNum;
	}

	static size_t NumMovePage(size_t alignNum)//计算一次性向PageCache要几页的span
	{
		assert(alignNum <= MAX_BYTE);
		size_t batchNum = NumMoveSize(alignNum);
		size_t totalByte = batchNum * alignNum;
		size_t npage = totalByte >> PAGE_SHFT;
		if (npage == 0)
			npage = 1;
		return npage;
	}
};

class Span
{
public:

	size_t _n = 0;//页数

	SPAN_ID _spanId = 0;//起始页编号

	//双指针结构
	Span* _prev = nullptr;
	Span* _next = nullptr;

	void* _freeList = nullptr;//拆分好的小内存块自由链表
	size_t _usedNum = 0;//拆分好的小内存块被ThreadCache使用量

	bool _isUsed = false;//有没有被使用

	size_t _nBlock = 0;//拆分好的小内存的大小
};

//带头双向循环链表
class SpanList
{
	Span* _head;

public:

	mutex _lock;//锁

	SpanList()
		:_head(new Span)
	{
		_head->_prev = _head;
		_head->_next = _head;
	}

	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);
		Span* prevSpan = pos->_prev;
		//prevSpan newSpan pos
		newSpan->_next = pos;
		newSpan->_prev = prevSpan;
		pos->_prev = newSpan;
		prevSpan->_next = newSpan;
	}

	void Erase(Span* pos)//将pos在SpanList中剔除就行，不用真的释放掉其内存
	{
		assert(pos);
		assert(pos->_next != pos);//不能删除头节点
		Span* prevSpan = pos->_prev;
		Span* nextSpan = pos->_next;
		//prevSpan pos nextSpan
		prevSpan->_next = nextSpan;
		nextSpan->_prev = prevSpan;
	}

	bool Empty()
	{
		return _head->_next == _head;
	}

	Span* Begin()
	{
		return _head->_next;
	}

	Span* End()
	{
		return _head;
	}

	void PushFront(Span* newSpan)
	{
		Insert(_head->_next, newSpan);
	}

	Span* PopFront()
	{
		Span* head = _head->_next;
		Erase(head);
		return head;
	}
};